package sum;

/**
 * 使用归并排序解决 求一个数组的最小和问题
 * 就是数组中每个数左边比它小的数的和，每个数得到这个值后，在求一个和
 * 就是数组的最小和
 * [1,2,3] 的最小和为  1 + 1 + 2 = 4
 *
 * @author Liaorun
 */
public class SmallSum {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(samllSum(arr));
    }

    public static int samllSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }

        return process(arr, 0, arr.length - 1);
    }

    /**
     * arr[l..r] 既要排好序，也要求小和
     *
     * @param arr 数组
     * @param l   左边的下标
     * @param r   右边的下标
     * @return 小和值
     */
    private static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }

        int mid = l + ((r - l) >> 1);

        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /**
     * 合并两个有序的数组，合并成一个有序的数组
     *
     * @param arr 一个数组 左边和右边分别有序
     * @param l   左边开始的下标
     * @param mid 中间位置
     * @param r   左边结束的下标
     * @return 小和
     */
    private static int merge(int[] arr, int l, int mid, int r) {
        // 辅助数组,和需要排序的部分一样大
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        int res = 0;

        // 当有一边的数全部取完了，就跳出循环
        while (p1 <= mid && p2 <= r) {
            // 左边的数比右边的小
            if (arr[p1] < arr[p2]) {
                // A = (r - p2 + 1) 是当前右边有多少个数比左边大
                // A * arr[p1] 左边的一个数本次merge产生的小和
                res += (r - p2 + 1) * arr[p1];
                help[i++] = arr[p1++];
            } else {
                // 左边的数不比右边的小
                res += 0;
                // 相等的情况下先把右边的拿下来
                // 如果先拿左边的，右边就可能存在和左边相等的数，
                // 就不能很快的知道有多少的数大于当前数
                help[i++] = arr[p2++];
            }
        }

        // 将剩下的数直接放到辅助数组
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }

        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

        // 将辅助数组的值放回原数组
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }

        // 返回本轮合并统计的小和
        return res;
    }
}
